package 栈与队列;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 前K个高频元素
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 *
 * 题目分析：
 *  要想找到前K个高频元素，
 *  有两种思路： 第一个是使用哈希表，遍历数组，统计出每个元素出现的频率，然后根据频率的高低，遍历这个map返回前K个元素。这种思路的时间复杂度是O(n)，空间复杂度是O(n)。
 *             第二个思路是使用优先队列，维护一个大小为K的小顶堆，遍历数组，对于每个元素，
 *             如果堆的元素小于K，则将该元素入堆，
 *             如果大于等于K，判断堆顶的元素频率是否小于当前元素的评率，如果小于，则移除堆顶元素，将该元素入堆。
 *             最后，从堆中取出所有元素，即为前K个高频元素。这种思路的时间复杂度是O(nlogk)，空间复杂度是O(k)。
 *解题步骤： 使用哈希表有空间复杂度O(n)的劣势，使用优先队列有空间复杂度O(k)的劣势，因此，综合考虑使用优先队列。
 *     1. 定义一个大小为K的小顶堆，使用优先队列实现，存放的元素是当前的元素及其评率。
 *     2. 定义一个数据结构，存放当前元素及其频率（键值对，使用HashMap）
 *     3： 遍历数组， 如果堆的大小小于K，则将该元素入堆。
 *                  如果堆的大小大于等于K，就判断堆顶元素的频率是否小于当前元素的频率，如果小于，则移除堆顶元素，将当前元素入堆。
 *     4: 最后，从堆中取出所有元素，即为前K个高频元素。
 * @Author lf
 * @Date 3/30/2024
 */
public class TopKFrequent {
    public int[] topKFrequent(int[] nums, int k) {
        // 定义一个数据结构，存放当前元素及其频率（键值对，使用HashMap）
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length ; i++) {
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        // 定义小顶堆，并设置小顶堆比较规则
        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b) -> {
            // 如果频率不同，按频率从小到达排列
            if(a[0] != b[0]){
                return  a[0] - b[0];
            }else { // 频率相同，按元素值从小到大排列
                return a[1]  - b[1];
            }
        });
        // 遍历Map容器，进行小顶堆的维护
        for (Map.Entry<Integer,Integer> entry:map.entrySet()){
            //频率
            Integer frequent = entry.getValue();
            //元素
            Integer element = entry.getKey();
            // 堆大小小于K，则将元素入堆
            if(queue.size() < k){
                queue.offer(new int[]{frequent,element});
            }else { // 堆的大小大于等于K的情况
                //堆顶元素的频率是否小于当前元素的频率，如果小于，则移除堆顶元素，将当前元素入堆。
                if(queue.peek()[0] < frequent){
                    // 移除堆顶元素
                    queue.poll();
                    // 将新元素入队
                    queue.offer(new int[]{frequent,element});
                }
            }
        }
        // 遍历小顶堆，返回结果
        int[] result =new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = queue.poll()[1];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        TopKFrequent solution = new TopKFrequent();
        int[] topK = solution.topKFrequent(nums, k);
        // 打印前K个高频元素
        for (int num : topK) {
            System.out.print(num + " ");
        }
    }
}
